package com.hunter;

import java.util.LinkedList;

/*
递归
 */
public class DiGui {

    public static void main(String[] args) {
        System.out.println(jiecheng(5)); // 求阶乘
        System.out.println("------");
        reversePrintString(0, "hunter");
        System.out.println("------");
        int[] nums = {3, 5, 2, 1};
        sort(nums, nums.length - 1);
        System.out.println("冒泡排序：");
        for (int num : nums) {
            System.out.println(num + " ");
        }
        System.out.println("------");

    }


    /*
    1.求阶乘
    **/
    public static int jiecheng(int n) {

        if (n == 1) {
            return 1;
        }
        return n * jiecheng(n - 1);
    }

    /*
    2.反向打印字符串
    * */
    public static void reversePrintString(int n, String str) {
        if (n == str.length()) {
            return;
        }
        reversePrintString(n + 1, str);
        System.out.println(str.charAt(n));
    }

    /*
    3.二分查找
    * */
    public static int search(int[] nums, int target) {
        return searchDigui(nums, target, 0, nums.length - 1);
    }

    // 用递归的方法实现二分查找
    private static int searchDigui(int[] nums, int target, int i, int j) {
        if (i > j) {
            return -1;
        }
        int m = (i + j) >>> 1;
        if (target < nums[m]) {
            return searchDigui(nums, target, i, m - 1);
        } else if (nums[m] > target) {
            return searchDigui(nums, target, m + 1, j);
        } else {
            return m;
        }
    }

    /*
    冒泡排序(一) 小到大排序
    * */

    private static void sort(int[] nums, int j) {
        // j代表右边界
        if (j == 0) {
            return;
        }
        for (int i = 0; i < j; i++) {
            if (nums[i] > nums[i + 1]) {
                int temp = nums[i];
                nums[i] = nums[i + 1];
                nums[i + 1] = temp;
            }
        }
        sort(nums, j - 1);
    }

    /*
    冒泡排序(二)
    * */
    private static void sort2(int[] nums, int j) {
        if (j == 0) {
            return;
        }
        int x = 0; // 左边界
        for (int i = 0; i < j; i++) {
            if (nums[i] > nums[i + 1]) {
                int temp = nums[i];
                nums[i] = nums[i + 1];
                nums[i + 1] = temp;
                x = i;
            }
        }
        sort2(nums, x);
    }

    /*
     插入排序算法实现
 */
    private static void insertionSort(int[] nums, int low) {
        // 索引 low 开始及其右边的元素（即 low 至 nums.length - 1）则是未排序的部分。
        // 如果low等于数组长度，则递归基成立，此时已经处理完所有元素
        if (low == nums.length) {
            return;
        }
        // 取出待排序的第一个元素
        int t = nums[low]; // t用来存储待插入的元素的值
        // 初始化已排序区域的指针
        int i = low - 1;

        // 当指针没有到达数组起始位置，并且当前元素大于待插入的元素时继续循环
        if (i >= 0 && nums[i] > t) {
            nums[i + 1] = nums[i];
            i--;
        }
        // 当退出循环时，找到了待插入元素的位置，将元素放置在该位置上
        nums[i + 1] = t;
        // 递归调用insertionSort，对下一个元素进行同样的操作
        insertionSort(nums, low + 1);
    }

    /*
    插入排序2
    当要找的元素就是low的时候，就不用这么麻烦了。因此，优化代码。
    **/
    private static void insertionSort2(int[] nums, int low) {
        if (low == nums.length) {
            return;
        }
        int t = nums[low]; // 待插入元素的值
        int i = low - 1;  // 已排序元素的指针
        if (i >= 0 && nums[i] > t) { // 没有找到插入位置
            nums[i + 1] = nums[i]; // 空出插入位置
            i--;
        }
        // 找到插入位置
        if (i + 1 != low) {
            nums[i + 1] = t;
        }
        insertionSort2(nums, low + 1);
    }

    /*
    多路递归 斐波那契数列
    之前的例子是每个递归函数只包含一个自身的调用，这称之为single recursion（单递归）
    如果每个递归函数例包含多个自身调用，称之为multi recursion（多输入递归）
    * */
    // 递归求斐波那契第n项
    public static int fibonacci(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        // 多输入递归
        int x = fibonacci(n - 1);
        int y = fibonacci(n - 2);
        return x + y;
    }

    /*
    多路递归 汉诺塔
    * n-圆盘个数
    * a-由
    * b-借
    * c-至
    **/

    // 初始化
    static void init(int n,LinkedList<Integer> a) {
        for (int i = n; i >= 1; i--) {
            a.addLast(i);
        }
    }

    static void move(int n, LinkedList<Integer> a,
                     LinkedList<Integer> b,
                     LinkedList<Integer> c) {
        if (n == 0) {
            return;
        }
        move(n - 1, a, c, b); // 把 n-1 个盘子由a，借c，移至b
        c.addLast(a.removeLast()); // 把最后的盘子 由a移动至c

        move(n - 1, b, a, c); // 把 n-1 个盘子由b，借a，移至c

    }
    private static void print() {
        System.out.println("-----");
        System.out.println();
        System.out.println();
        System.out.println();
    }



}